/// @tags: OverallDiv
#include <algorithm>
#include <cstdio>
#include <iostream>

using std::cin, std::cout;

namespace BlueQuantum {

constexpr int maxn = 5e2 + 1, maxq = 6e4 + 1;

struct Node {
  int x, y, val;
  bool operator<(const Node &rhs) const { return val < rhs.val; }
};

struct Query {
  int x1, y1, x2, y2, k, id, cur;
};

int n, q;

class TreeArray {
 private:
  int data[maxn][maxn];

  int lowbit(int x) { return x & -x; }

  int query(int x, int y) {
    int res = 0;
    for (; x; x -= lowbit(x))
      for (int j = y; j; j -= lowbit(j)) res += data[x][j];
    return res;
  }

 public:
  void add(int x, int y, int val) {
    for (; x <= n; x += lowbit(x))
      for (int j = y; j <= n; j += lowbit(j)) data[x][j] += val;
  }

  int query(Query qry) {
    return query(qry.x2, qry.y2) - query(qry.x1 - 1, qry.y2) - query(qry.x2, qry.y1 - 1) +
           query(qry.x1 - 1, qry.y1 - 1);
  }
};

int ans[maxq];
Node matrix[maxn * maxn];
Query queries[maxq];
TreeArray bit;

void solve(int l, int r, int query_l, int query_r) {
  static Query tmp[maxq];
  if (query_l > query_r) return;
  if (l == r) {
    for (int i = query_l; i <= query_r; ++i) ans[queries[i].id] = matrix[l].val;
    return;
  }
  int mid = (l + r) / 2;
  for (int i = l; i <= mid; ++i) {
    bit.add(matrix[i].x, matrix[i].y, 1);
  }
  int cnt1 = 0, cnt2 = q + 1;
  for (int i = query_l; i <= query_r; ++i) {
    int sum = queries[i].cur + bit.query(queries[i]);
    if (sum >= queries[i].k)
      tmp[++cnt1] = queries[i];
    else
      queries[i].cur = sum, tmp[--cnt2] = queries[i];
  }
  for (int i = 1; i <= cnt1; ++i) queries[query_l + i - 1] = tmp[i];
  for (int i = cnt2; i <= q; ++i) queries[query_r - (i - cnt2)] = tmp[i];
  for (int i = l; i <= mid; ++i) {
    bit.add(matrix[i].x, matrix[i].y, -1);
  }
  solve(l, mid, query_l, query_l + cnt1 - 1);
  solve(mid + 1, r, query_l + cnt1, query_r);
}

int main() {
  cin >> n >> q;
  for (int i = 1, cnt = 0; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> matrix[++cnt].val;
      matrix[cnt].x = i, matrix[cnt].y = j;
    }
  }
  std::sort(matrix + 1, matrix + n * n + 1);
  for (int i = 1; i <= q; ++i) {
    cin >> queries[i].x1 >> queries[i].y1 >> queries[i].x2 >> queries[i].y2 >> queries[i].k;
    queries[i].id = i;
  }
  solve(1, n * n, 1, q);
  for (int i = 1; i <= q; ++i) cout << ans[i] << std::endl;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P1527 [国家集训队] 矩阵乘法.in", "r", stdin);
  freopen("P1527 [国家集训队] 矩阵乘法.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
